package cn.javadog.algorithm.m1_100;


/**
 * 最长回文子串
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @author Sprite
 */
public class Algorithm5 {
	public static void main(String[] args) {
//		System.out.println(longestPalindrome("babad"));
//		System.out.println(longestPalindrome("cbbd"));
//		System.out.println(longestPalindrome("abc"));
//		System.out.println(longestPalindrome("a"));
//		System.out.println(longestPalindrome(""));
//		System.out.println(longestPalindrome("aaaaaaa"));
		System.out.println(longestPalindrome("aaaaaa"));
	}

	public static String longestPalindrome(String s) {
		char[] chars = s.toCharArray();
		int length = chars.length;
		int maxIdx;
		int maxLength = 0;
		String pal = "";
		for (int i = 0; i < length; i++) {
			// 单回文，如aba
			maxIdx = Math.min(i,chars.length-1-i);
			for (int j = 1; j <= maxIdx; j++) {
				if (chars[i+j] != chars[i-j]) break;
				else if (2*j+1 > maxLength){
					maxLength = 2*j+1;
					pal = s.substring(i-j,i+j+1);
				}
			}
			if (pal.length() < 2) pal = String.valueOf(chars[i]);

			// 双回文，如abba
			if (i<length-1 && chars[i] == chars[i+1]){
				maxIdx = Math.min(i,chars.length-2-i);
				for (int j = 1; j <= maxIdx; j++) {
					if (chars[i+j+1] != chars[i-j]) break;
					else if (2*j+2 > maxLength){
						maxLength = 2*j+2;
						pal = s.substring(i-j,i+j+2);
					}
				}
				if (pal.length() < 3) pal = s.substring(i,i+2);
			}
		}
		return pal;
	}
}
